This invention relates to control circuits using a linear mutual exclusion chain, and in particular to a circuit for controlling pipeline stages in asynchronous systems. The chain provides asynchronous `turns` to a group of counterflow pipeline stages. The chain of mutual exclusion elements enables action in any stage to exclude action in the two neighboring stages. In some cases stages receive two turns in succession, inhibiting their neighbors for the longer interval required for the two actions. The control circuit described allows such an asynchronous system to operate at very high speeds, for example, on the order of about 700 Mhz or more.
Counterflow pipeline processors are well known. Counterflow pipeline processors are computer system processors in which instructions and results flow in opposite directions within a pipeline and interact as they pass. In counterflow pipeline processors, a pipeline is formed from stages, each of which includes an instruction portion and a results portion. Instructions flow in one direction through the pipeline, while results flow in the other direction. In such systems the operation of the various stages with respect to each other must be controlled to assure that instructions and results are transferred at appropriate times when the destination is able to receive them and act upon them.
A more detailed discussion of prior work on counterflow pipeline processors is described in a publication "Counterflow Pipeline Processor Architecture" available from Sun Microsystems, assignee of this invention, as report SMLI TR-94-25. It is also the subject of commonly-assigned U.S. Pat. No. 5,187,800, entitled "Asynchronous Pipelined Data Processing System." In such systems it is important to assure that the instructions and the results interact properly within each stage and that each stage is not provided with more data during the interaction process. Therefore a suitable control system to allow the stages to communicate properly is necessary. The circuit of this invention provides such a mechanism.
Also known are circuits to provide mutual exclusion between two contenders. Such circuits are described, for example, in Chapter 7 entitled "System Timing," Section 7.8.6 (pp. 260-261) of Introduction to VLSI Systems, by Mead and Conway (Addison Wesley, 1980), and elsewhere. As depicted therein, one basis for such circuits is a flip flop and a threshold detector. Each of the two contenders for service attempts to place the flip flop in the state favoring its service. The problem, of course, is that the two contenders might both request service at the same time, leaving the flip flop in a "metastable" state where it is neither flipped nor flopped. The threshold detector is designed so that it will announce success in the choice only when the flip flop has left the metastable region and is firmly flipped or flopped.